# 给你一棵以 root 为根的 二叉树 ，请你返回 任意 二叉搜索子树的最大键值和。
#
#  二叉搜索树的定义如下：
#  任意节点的左子树中的键值都 小于 此节点的键值。
#  任意节点的右子树中的键值都 大于 此节点的键值。
#  任意节点的左子树和右子树都是二叉搜索树。
#
#  示例 1：
# 输入：root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
# 输出：20
# 解释：键值为 3 的子树是和最大的二叉搜索树。
#
#  示例 2：
# 输入：root = [4,3,null,1,2]
# 输出：2
# 解释：键值为 2 的单节点子树是和最大的二叉搜索树。
#
#  示例 3：
# 输入：root = [-4,-2,-5]
# 输出：0
# 解释：所有节点键值都为负数，和最大的二叉搜索树为空。
#
#
#  示例 4：
# 输入：root = [2,1,3]
# 输出：6
#
#  示例 5：
# 输入：root = [5,4,8,3,null,6,3]
# 输出：7
import sys

from com.example.tree.tree_node import TreeNode
from typing import Optional


class Solution:
    def maxSumBST1(self, root: TreeNode) -> int:
        min_, max_, res = -sys.maxsize - 1, sys.maxsize, 0

        def postOrder(root: TreeNode) -> (int, int, int):
            """
            根据后序遍历判断是否是BST变形来的(leetcode98)
            :param root:
            :return:
            """
            if not root:
                return max_, min_, 0

            leftMinVal, leftMaxVal, leftSum = postOrder(root.left)
            rightMinVal, rightMaxVal, rightSum = postOrder(root.right)

            if leftMaxVal < root.val < rightMinVal:  # 满足二叉搜素树的条件
                nonlocal res
                res = max(res, root.val + leftSum + rightSum)
                return min(leftMinVal, root.val), max(rightMaxVal, root.val), root.val + leftSum + rightSum
            return min_, max_, 0

        postOrder(root)
        return res


    def maxSumBST(self, root: Optional[TreeNode]) -> int:
        return self.maxSumBST1(root)


if __name__ == "__main__":
    #                                               1
    #                   4                                                          3
    #        2                    4                                2                             5
    #                                                                                     4              6
    root = TreeNode(1)
    root.left, root.right = TreeNode(4), TreeNode(3)
    root.left.left, root.left.right, root.right.left, root.right.right = TreeNode(2), TreeNode(4), TreeNode(2), TreeNode(5)
    root.right.right.left, root.right.right.right = TreeNode(4), TreeNode(6)
    #                                              5
    #                    4                                                   8
    #        3                                                   6                          3
    # root = TreeNode(5)
    # root.left, root.right = TreeNode(4), TreeNode(8)
    # root.left.left, root.right.left, root.right.right = TreeNode(3), TreeNode(6), TreeNode(3)
    print(Solution().maxSumBST1(root))
